/*
 * @lc app=leetcode.cn id=390 lang=cpp
 *
 * [390] 消除游戏
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int lastRemaining(int n)
    {
        vector<int> v[2];
        for (int i = 1; i <= n; i++)
        {
            v[0].push_back(i);
        }

        int flag = 0;
        while (v[0].size() + v[1].size() > 1)
        {
            if (flag == 0)
            {
                for (int i = 1; i < v[0].size(); i += 2)
                {
                    v[1].push_back(v[0][i]);
                }
            }
            else
            {
                for (int i = v[1].size() - 2; i >= 0; i -= 2)
                {
                    v[0].push_back(v[1][i]);
                }
                std::reverse(v[0].begin(), v[0].end());
            }
            v[flag].clear();
            flag = 1 - flag;
        }
        if (v[0].size())
            return v[0][0];
        else
            return v[1][0];
    }
};

int main()
{
    for (int i = 1; i <= 100; i++)
        cout << i << " : " << Solution().lastRemaining(i) << endl;
    return 0;
}

// @lc code=end
